/*
Date:20220227 18:51 PM
key:关键是有一条路通就行。所以不用四条路去或。有一条ok就返回。
*/
class Solution {
public:
    bool search(vector<vector<char>>& board,int x,int y,int pos,string&word)
    {
        //当前字符符合word字符
        //cout<<"x: "<<x<<"y: "<<y<<"pos :"<<pos<<endl;
        if(x<0||x>=board.size()||y<0||y>=board[0].size()||board[x][y]=='0'){return false;}

        if(board[x][y]==word[pos])
        {
            if(pos==word.size()-1)
            {
                //cout<<"yes"<<board[x][y];
                return true;
            }
            else
            {
                
                char tmp=board[x][y];
                board[x][y]='0';
                bool up=false,down=false,left=false,right=false;
                
                
                    up=search(board,x-1,y,pos+1,word);
                    if(up){return true;}
                    down=search(board,x+1,y,pos+1,word);
                    if(down){return true;}
                    left=search(board,x,y-1,pos+1,word);
                    if(left){return true;}
                    right=search(board,x,y+1,pos+1,word);
                    if(right){return true;}
                    board[x][y]=tmp;
                
                
                return false;
            }
        }else
        {
            return false;
        }
        
    }
    bool exist(vector<vector<char>>& board, string word) {
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[0].size();j++)
            {
                if(word[0]!=board[i][j]){continue;}
                if(search(board,i,j,0,word)){return true;}
                //cout<<"nex start: "<<endl;
            }
        }
        return false;
    }
};

